package com.qrpcw.algorithms;

public class MaximumSubarray1 {

	/**
	 * Maximum-Subarray
	 * Brute-Force solution
	 * o(n^2)
	 * @param args
	 */
	public static void main(String[] args) {
		int[] a = new int[]{13,-3,-25,-20,-3,-16,-23,18,20,-7,12,-5,-22,15,-4,7};
		MaximumSubarray1 test = new MaximumSubarray1();
		int maxSum = test.maxSubarray(a);
		System.out.println(maxSum);
	}
	
	public int maxSubarray(int[] a){
		int i,j;
		int maxSum=0;
		for (i=0; i<a.length; i++){
			int sum = 0;
			for (j=i; j<a.length; j++){
				sum = sum + a[j];
				maxSum = (maxSum > sum)?maxSum:sum;
			}
		}
		return maxSum;
	}
}


